// dij(2 * (v + E))

struct Dijkstra {
    using i64 = long long;
    struct edge {
        int to, next; 
        i64 dis;
    };
 
    std::vector<edge> e;
    std::vector<int> head;
    std::vector<i64> dis;
    std::vector<bool> vis;
    int cnt;
    Dijkstra(int n) {
        init(n);
    }

    void init(int n) {
        cnt = 0;
        head.assign(n + 10, 0);
        vis.assign(n + 10, false);
        dis.assign(n + 10, 1e18);
        e.assign(n + 10, {});
    }
 
    void add_edge(int u, int v, i64 d) {
        cnt++;
        e[cnt].dis = d;
        e[cnt].to = v;
        e[cnt].next = head[u];
        head[u] = cnt;
    }
 

    struct node {
        i64 dis;
        int pos;
        bool operator <(const node &x) const {
            return x.dis < dis;
        }
    };
 
    std::priority_queue<node> q;
    void work(int r) {
        dis[r] = 0;
        q.push((node){0, r});
 
        while(!q.empty()) {
            node tmp = q.top();
            q.pop();
            int x = tmp.pos;
            i64 d = tmp.dis;
 
            if (vis[x]) {
                continue;
            }
 
            vis[x] = 1;
            for (int i = head[x]; i; i = e[i].next) {
                int y = e[i].to;
                if (dis[y] > dis[x] + e[i].dis) {
                    dis[y] = dis[x] + e[i].dis;
                    if (!vis[y]) {
                        q.push((node){dis[y], y});
                    }
                }
            }
        }
    }
};